package com.gjy.ds.sort_search;

/**
 * @author 宫静雨
 * @version 1.0
 * @since 2022-12-15 16:55:35
 */
public class Search {

    /**
     * 线性查找
     *
     * @param array 待查找元素的数组
     * @param v     待查找的元素
     * @return 元素下标
     */
    public int seq(int[] array, int v) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == v) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 二分法查找
     *
     * @param array 待查找元素的数组
     * @param v     待查找的元素
     * @return 元素下标
     */
    public int binary(int[] array, int v) {
        return binary(array, 0, array.length - 1, v);
    }

    /**
     * 二分法查找
     *
     * @param array 待查找元素的数组
     * @param v     待查找的元素
     * @return 元素下标
     */
    public int binary(int[] array, int l, int r, int v) {
        if (l > r) {
            throw new IllegalArgumentException();
        }
        while (l <= r) {
            int m = (l + r) >> 1;
            if (array[m] > v) {
                r = m - 1;
            } else if (array[m] < v) {
                l = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 插值查找
     */
    public int insert(int[] array, int l, int r, int v) {

        if (l > r || array[0] > v || array[array.length - 1] < v) {
            return -1;
        }

        int m = l + (r - l) * (v - array[l]) / (array[r] - array[l]);
        if (v > array[m]) {
            return insert(array, m + 1, r, v);
        } else if (v < array[m]) {
            return insert(array, l, m - 1, v);
        } else {
            return m;
        }
    }

    private int[] fib(int size) {
        int[] f = new int[size];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < size; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    public int fib(int[] array, int v) {
        int low = 0, high = array.length - 1, k = 0, mid = 0;
        int[] f = fib(array.length);

        return -1;
    }
}
